/*
 * @lc app=leetcode.cn id=LCR 155 lang=cpp
 * @lcpr version=30204
 *
 * [LCR 155] 将二叉搜索树转化为排序的双向链表
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution
{
public:
    Node *treeToDoublyList(Node *root)
    {
        /* 方法一：将中序遍历的结果利用数组存储，然后再组织成为双向链表
        InOrder(root);
        int n = v.size();
        if(n==0) return nullptr;
        for (int i = 0; i < n-1; ++i)
        {
            v[i]->right = v[i+1];
            v[i+1]->left = v[i];
        }
        v[0]->left = v[n-1];
        v[n-1]->right = v[0];
        return v[0];
        */

        // 方法二：递归过程中就将双向链表建立好
        if(root == nullptr) return nullptr;
        DFS(root);
        head->left = prev;
        prev->right = head;
        return head;
    }

private:
    /*
    vector<Node *> v;
    void InOrder(Node *root)
    {
        if (root == nullptr)
            return;
        InOrder(root->left);
        v.push_back(root);
        InOrder(root->right);
    }
    */
    Node *prev, *head;
    void DFS(Node *cur)
    {
        if (cur == nullptr)
            return;
        DFS(cur->left);
        if (prev != nullptr)
            prev->right = cur;
        else
            head = cur;
        cur->left = prev;
        prev = cur;
        DFS(cur->right);
    }
};
// @lc code=end

/*
// @lcpr case=start
// [4,2,5,1,3]\n
// @lcpr case=end

// @lcpr case=start
// [2,1,3]\n
// @lcpr case=end

// @lcpr case=start
// []\n
// @lcpr case=end

// @lcpr case=start
// [1]\n
// @lcpr case=end

 */
